/**
 * https://leetcode-cn.com/problems/minimum-window-substring/
 */
public class Solution {
    public String minWindow(String s, String t) {
        if (s == null || "".equals(s) || t == null || "".equals(t))
            return "";
        int[] dict = new int[128];
        int count = t.length();
        for (int i = 0; i < t.length(); i++) {
            dict[t.charAt(i)]++;
        }
        char[] arr = s.toCharArray();
        int left = 0, right = 0, windowSize = Integer.MAX_VALUE, start = 0;
        while (right < arr.length) {
            if (dict[arr[right]] > 0) {
                // 如果是指定字符 count 就 -1
                count--;
            }
            // 在 left 和 right 之间的都 -1
            dict[arr[right]]--;
            if (count == 0) {
                // count 为 0 表示 left 和 right 之间包含了所有的字符
                while (left < right && dict[arr[left]] < 0) {
                    // 开始移动左边指针
                    dict[arr[left]]++;
                    left++;
                }
                if (right - left + 1 < windowSize) {
                    windowSize = right - left + 1;
                    start = left;
                    // System.out.println("start : " + start + " windowSize : " + windowSize);
                }
                dict[arr[left++]]++;
                count++;
            }
            right++;
        }
        if (windowSize != Integer.MAX_VALUE) {
            return s.substring(start, start + windowSize);
        }
        return "";
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minWindow("ADOBECODEBANC", "ABC"));
    }
}
